package leetcode.primary;

public class T215 {
    public int findKthLargest(int[] nums, int k) {
        int left = 0,right = nums.length-1;
        int target = nums.length-k;
        while (true){
            int index = partition(nums, left, right);
            if (index==target){
               break;
            }

            if (index>target){
                right = index-1;
            }else {
                left = index+1;
            }
        }
       return nums[target];
    }

    public int partition(int[] nums,int left,int right){
        if (left>=right){
            return left;
        }
        int temp = nums[left];
        int i = left,j = right;
        while (i<j){
            while (j>i && nums[j]>temp){
                j--;
            }
            while (j>i && nums[i]<=temp){
                i++;
            }
            if (i<j){
                swag(i,j,nums);
            }
        }
        swag(i,left,nums);
        return i;
    }

    public void swag(int i,int j,int[] nums){
        if (i==j){
            return;
        }
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        T215 t215 = new T215();
        int kthLargest = t215.findKthLargest(new int[]{3,2,3,1,2,4,5,5,6}, 4);
        System.out.println(kthLargest);
    }
}
